package 二叉树;

import java.util.Deque;
import java.util.LinkedList;

/**
 * https://leetcode-cn.com/problems/recover-a-tree-from-preorder-traversal/
 * 依次遍历里面的每个值把值拟成数的节点放入栈中，在深度和当前元素不匹配时清除
 * （一个横杠深度是1此时里面只能有1个元素，在最后把多余的节点清出栈，方便下一个节点值进行入栈时的操作）
 */
public class 从先序遍历还原二叉树 {
    public TreeNode recoverFromPreorder(String traversal) {
        Deque<TreeNode> stack = new LinkedList<>();
        for (int i = 0; i < traversal.length();) {
            int val = 0;
            while (i < traversal.length() && Character.isDigit(traversal.charAt(i))){
                val = val * 10 + traversal.charAt(i ++ ) - '0';
            }
            TreeNode node = new TreeNode(val);
            if (!stack.isEmpty()){
                if (stack.peek().left == null) {
                    stack.peek().left = node;
                }else {
                    stack.peek().right = node;
                }
            }
            //走到这里说明栈为空
            stack.push(node);
            if (i >= traversal.length()){
                break;
            }
            int depth = 0;
            while (traversal.charAt(i) == '-'){
                i++;
                depth++;
            }
            while (stack.size() > depth){
                stack.pop();
            }
        }
        return stack.peekLast();
    }
}
